package primary.code05_Tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Yudi Wang
 * @date 2021/7/12 17:28
 * <p>
 * 判断 满二叉树(高低为k, 节点数为2^k-1)
 */
public class Code06_FullBinaryTree {

    /**
     * DP
     *
     * @param head
     * @return
     */
    private static ReturnData judgeFBT2(Node head) {
        if (head == null) {
            return new ReturnData(true, 0);
        }
        //返回可以判断结果的数据即可，而并非要直接返回结果
        ReturnData leftData = judgeFBT2(head.left);
        ReturnData rightData = judgeFBT2(head.right);
        if (leftData.isFullTree && rightData.isFullTree
                && (leftData.height == rightData.height)) {
            return new ReturnData(true, leftData.height + 1);
        } else {
            return new ReturnData(false, -1);
        }
    }

    private static ReturnData judgeFBT2Test(Node head) {
        if (head == null) {
            return new ReturnData(true, 0);
        }
        ReturnData lrd = judgeFBT2Test(head.left);
        ReturnData rrd = judgeFBT2Test(head.right);
        boolean isFullTree = lrd.isFullTree && rrd.isFullTree && lrd.height == rrd.height;
        return new ReturnData(isFullTree, Math.max(lrd.height, rrd.height) + 1);
    }

    /**
     * 计算每层的节点数量
     *
     * @param head
     * @return
     */
    private static boolean judgeFBT1(Node head) {
        if (head == null) return true;
        Queue<Node> queue = new LinkedList<>();
        Node end = head;//当前层最后节点
        Node nextEnd = null;//下层最后节点
        int level = 0;//当前层
        int cnt = 0;//当前层数量
        queue.add(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            cnt++;
            if (cur.left != null) {
                queue.add(cur.left);
                nextEnd = cur.left;

            }
            if (cur.right != null) {
                queue.add((cur.right));
                nextEnd = cur.right;
            }
            if (cur == end) {
                if ((1 << level) != cnt) {
                    return false;
                } else {
                    end = nextEnd;
                    nextEnd = null;
                    level++;
                    cnt = 0;
                }
            }
        }
        return true;
    }

    private static boolean judgeFBT1Test(Node head) {
        if (head == null) return true;

        int curLevel = 0;
        int curLevelNodeCount = 0;
        Node curLevelLastNode = head;
        Node nextLevelLastNode = null;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
                nextLevelLastNode = cur.left;
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                nextLevelLastNode = cur.right;
            }
            curLevelNodeCount++;
            // 结算
            if (cur == curLevelLastNode) {
                if (Math.pow(2, curLevel) != curLevelNodeCount) {
                    return false;
                }
                curLevel++;
                curLevelNodeCount = 0;
                curLevelLastNode = nextLevelLastNode;
                nextLevelLastNode = null;
            }
        }
        return true;
    }

    static class ReturnData {
        //是否为满二叉树
        private boolean isFullTree;
        //树高度
        private int height;

        public ReturnData(boolean isFullTree, int height) {
            this.isFullTree = isFullTree;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.right.left = new Node(7);//注释则为非满二叉树
        head.right.right = new Node(9);
        boolean res1 = judgeFBT1Test(head);
        System.out.println("judgeFBT1Test, is FBT: " + res1);

        ReturnData returnData = judgeFBT2Test(head);
        System.out.println("judgeFBT2Test, is FBT: " + returnData.isFullTree);
    }
}
